{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Black Square LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSquare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大黑方阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。</p>\n",
    "\n",
    "<p>返回一个数组 <code>[r, c, size]</code> ，其中&nbsp;<code>r</code>,&nbsp;<code>c</code>&nbsp;分别代表子方阵左上角的行号和列号，<code>size</code> 是子方阵的边长。若有多个满足条件的子方阵，返回 <code>r</code> 最小的，若 <code>r</code> 相同，返回 <code>c</code> 最小的子方阵。若无满足条件的子方阵，返回空数组。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:\n",
    "</strong>[\n",
    "&nbsp;  [1,0,1],\n",
    "&nbsp;  [<strong>0,0</strong>,1],\n",
    "&nbsp;  [<strong>0,0</strong>,1]\n",
    "]\n",
    "<strong>输出: </strong>[1,0,2]\n",
    "<strong>解释: </strong>输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:\n",
    "</strong>[\n",
    "&nbsp;  [<strong>0</strong>,1,1],\n",
    "&nbsp;  [1,0,1],\n",
    "&nbsp;  [1,1,0]\n",
    "]\n",
    "<strong>输出: </strong>[0,0,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>matrix.length == matrix[0].length &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-black-square-lcci](https://leetcode.cn/problems/max-black-square-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-black-square-lcci](https://leetcode.cn/problems/max-black-square-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "\t\tdef check(r, c, size):\n",
    "\t\t\tfor i in range(c, c + size):\n",
    "\t\t\t\tif matrix[r][i] or matrix[r + size - 1][i]:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\tfor i in range(r + 1, r + size - 1):\n",
    "\t\t\t\tif matrix[i][c] or matrix[i][c + size - 1]:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\treturn True\n",
    "\n",
    "\t\tfor size in range(len(matrix), 0, -1):\n",
    "\t\t\tfor r in range(0, len(matrix) - size + 1):\n",
    "\t\t\t\tfor c in range(0, len(matrix) - size + 1):\n",
    "\t\t\t\t\tif check(r, c, size):\n",
    "\t\t\t\t\t\treturn [r, c, size]\n",
    "\t\treturn []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "\n",
    "        # 预处理前缀和\n",
    "        prefix_right = [[0] * n for _ in range(n)]  # 表示包括(i, j)在内的右边有多少个连续的0\n",
    "        prefix_down =  [[0] * n for _ in range(n)]  # 表示包括(i, j)在内的下边有多少个连续的0\n",
    "        for i in range(n):\n",
    "            prefix_right[i][-1] = int(matrix[i][-1] == 0)\n",
    "            prefix_down[-1][i] = int(matrix[-1][i] == 0)\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    prefix_right[i][j] = prefix_right[i][j + 1] + 1\n",
    "                if matrix[j][i] == 0:\n",
    "                    prefix_down[j][i] = prefix_down[j + 1][i] + 1\n",
    "\n",
    "        # 返回边长为size的最小下标子方针 若不存在返回None\n",
    "        def get_sub(size: int) -> List[int]:\n",
    "            # 枚举每一个起点\n",
    "            for i in range(n - size + 1):\n",
    "                for j in range(n - size + 1):\n",
    "                    if prefix_right[i][j] >= size and prefix_down[i][j] >= size and prefix_right[i + size - 1][j] >= size and prefix_down[i][j + size - 1] >= size:\n",
    "                        return [i, j, size]\n",
    "            return None\n",
    "\n",
    "        # 二分答案\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if get_sub(mid) is None:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return get_sub(right) if right > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "\t\tdef check(r, c, size):\n",
    "\t\t\tfor i in range(c, c + size):\n",
    "\t\t\t\tif matrix[r][i] or matrix[r + size - 1][i]:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\tfor i in range(r + 1, r + size - 1):\n",
    "\t\t\t\tif matrix[i][c] or matrix[i][c + size - 1]:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\treturn True\n",
    "\n",
    "\t\tfor size in range(len(matrix), 0, -1):\n",
    "\t\t\tfor r in range(0, len(matrix) - size + 1):\n",
    "\t\t\t\tfor c in range(0, len(matrix) - size + 1):\n",
    "\t\t\t\t\tif check(r, c, size):\n",
    "\t\t\t\t\t\treturn [r, c, size]\n",
    "\t\treturn []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        # dp————这种题目就是烦！\n",
    "        n = len(matrix)\n",
    "        left = [[0]*(n+1) for _ in range(n+1)]\n",
    "        up = [[0]*(n+1) for _ in range(n+1)]\n",
    "        r,c,size =0,0,0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    border = min(left[i][j],up[i][j])\n",
    "                    while left[i-border+1][j] < border or up[i][j-border+1]<border:\n",
    "                        border -= 1\n",
    "                    if border >size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r,c,size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "\n",
    "        up = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        left = [[0 for _ in range(col)] for _ in range(row)]\n",
    "\n",
    "        ans = 0\n",
    "        res = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == 0:\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    for bc in range(1, min(up[i][j], left[i][j])+1):\n",
    "                        if left[i-bc+1][j] >= bc and up[i][j-bc+1] >= bc:\n",
    "                            if bc > ans:\n",
    "                                ans = bc\n",
    "                                res = [i-bc+1, j-bc+1, ans]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = [0, 0, 0]\n",
    "        x = [[0] * n for _ in range(m)]\n",
    "        y = [[0] * n for _ in range(n)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    x[i][j] = x[i][j + 1] + 1 if j + 1 < n else 1\n",
    "                    y[i][j] = y[i + 1][j] + 1 if i + 1 < m else 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(ans[2] + 1, min(m - i + 1, n - j + 1)):\n",
    "                    if x[i][j] >= k and x[i + k - 1][j] >= k and y[i][j] >= k and y[i][j + k - 1] >= k:\n",
    "                        ans = [i, j, k]\n",
    "\n",
    "        return ans if ans[2] > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0]*(n+1) for _ in range(n+1)]\n",
    "        up = [[0]*(n+1) for _ in range(n+1)]\n",
    "        ans,ret = 0,[]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    length = min(left[i][j], up[i][j])\n",
    "                    while left[i-length+1][j] < length or up[i][j-length+1] < length:\n",
    "                        length -= 1\n",
    "                    if length > ans:\n",
    "                        ans = length\n",
    "                        ret = [i-length,j-length,length]\n",
    "        #print(left,up)\n",
    "        return ret\n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        # 初始化辅助矩阵\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        \n",
    "        # 初始化结果变量\n",
    "        r, c, size = 0, 0, 0\n",
    "        \n",
    "        # 遍历原始矩阵\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:  # 若当前像素是黑色（用0表示）\n",
    "                    # 更新辅助矩阵的值\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    \n",
    "                    # 计算以当前像素为右下角的子方阵的最大可能边长\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    \n",
    "                    # 验证是否真的可以形成一个全黑的子方阵\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                        \n",
    "                    # 更新结果\n",
    "                    if border > size:\n",
    "                        r, c, size = i - border, j - border, border\n",
    "\n",
    "        # 返回结果\n",
    "        return [r, c, size] if size > 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        right = [[0] * n for _ in range(n)]\n",
    "        down = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    right[i][j] = right[i][j + 1]\n",
    "                    if matrix[i][j + 1] == 0:\n",
    "                        right[i][j] += 1\n",
    "        for j in range(n):\n",
    "            for i in range(n - 2, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    down[i][j] = down[i + 1][j]\n",
    "                    if matrix[i + 1][j] == 0:\n",
    "                        down[i][j] += 1\n",
    "        ans = [-1, -1, 0]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] != 0:\n",
    "                    continue\n",
    "                for k in range(min(right[i][j], down[i][j]), -1, -1):\n",
    "                    if down[i][j + k] >= k and right[i + k][j] >= k:\n",
    "                        if k + 1 > ans[-1]:\n",
    "                            ans = [i, j, k + 1]\n",
    "                        break\n",
    "        return ans if ans[-1] > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if len(matrix) == 0:\n",
    "            return []\n",
    "        n = len(matrix)\n",
    "        right = [[0] * n for each in range(n)]\n",
    "        down = [[0] * n for each in range(n)]\n",
    "        for i in range(n):\n",
    "            right_last_one = n\n",
    "            down_last_one = n\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    right[i][j] = right_last_one - j\n",
    "                elif matrix[i][j] == 1:\n",
    "                    right_last_one = j\n",
    "                if matrix[j][i] == 0:\n",
    "                    down[j][i] = down_last_one - j\n",
    "                elif matrix[j][i] == 1:\n",
    "                    down_last_one = j\n",
    "\n",
    "        ans, r, c = 0, 0, 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                minn = min(down[i][j], right[i][j])\n",
    "                temp = 0\n",
    "                for k in range(minn, -1, -1):\n",
    "                    if right[i + k - 1][j] >= k and down[i][j + k - 1] >= k:\n",
    "                        temp = k\n",
    "                        break\n",
    "                if temp > ans:\n",
    "                    ans, r, c = temp, i, j\n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "        if ans == 0:\n",
    "            return []\n",
    "        else:\n",
    "            return[r, c, ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix) + 1\n",
    "        up = [[0] * n for _ in range(n)]\n",
    "        left = [[0] * n for _ in range(n)]\n",
    "        r = c = 0\n",
    "        max_len = 0 \n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n): \n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    up[i][j] = up[i-1][j] + 1 \n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "\n",
    "                    board = min(left[i][j], up[i][j])\n",
    "                    while left[i-board+1][j] < board or up[i][j-board+1] < board:\n",
    "                        board -= 1 \n",
    "                    if max_len < board:\n",
    "                        max_len = board \n",
    "                        r = i-board\n",
    "                        c = j-board\n",
    "                    \n",
    "        return [r,c,max_len] if max_len>0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        cols = len(matrix) + 1\n",
    "        left = [[0] * cols for _ in range(cols)]\n",
    "        up = [[0] * cols for _ in range(cols)]\n",
    "\n",
    "        r = c = 0\n",
    "        size = 0 \n",
    "        for i in range(1, cols):\n",
    "            for j in range(1, cols):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1 \n",
    "                    board = min(left[i][j], up[i][j])\n",
    "                    while left[i-board+1][j] < board or up[i][j-board+1] < board:\n",
    "                        board -= 1\n",
    "                    if size < board:\n",
    "                        r = i-board\n",
    "                        c = j-board \n",
    "                        size = board\n",
    "        \n",
    "        return [r, c, size] if size > 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        up = [[0] * (n+1) for _ in range(n+1)]\n",
    "        left = [[0] * (n+1)  for _ in range(n+1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    left[i][j] = left[i][j-1] + 1 \n",
    "                    border = min(up[i][j], left[i][j])\n",
    "                    while left[i-border+1][j] < border or up[i][j-border+1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r,c,size] if size > 0 else []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        cols = len(matrix) + 1\n",
    "        left = [[0] * cols for _ in range(cols)]\n",
    "        up = [[0] * cols for _ in range(cols)]\n",
    "\n",
    "        r = c = 0\n",
    "        size = 0 \n",
    "        for i in range(1, cols):\n",
    "            for j in range(1, cols):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1 \n",
    "                    board = min(left[i][j], up[i][j])\n",
    "                    while left[i-board+1][j] < board or up[i][j-board+1] < board:\n",
    "                        board -= 1\n",
    "                    if size < board:\n",
    "                        r = i-board\n",
    "                        c = j-board \n",
    "                        size = board\n",
    "        \n",
    "        return [r, c, size] if size > 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n+1) for _ in range(n+1)]\n",
    "        up = [[0] * (n+1) for _ in range(n+1)]\n",
    "        size = 0\n",
    "        r = 0\n",
    "        c = 0\n",
    "        for i in range(1, n+1) :\n",
    "            for j in range(1, n+1) :\n",
    "                if matrix[i-1][j-1] == 0 :\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i-border+1][j] < border or up[i][j-border+1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        size = border\n",
    "                        r = i - border \n",
    "                        c = j - border \n",
    "        if size == 0:\n",
    "            return []\n",
    "        return [r, c, size]\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        cols = len(matrix) + 1\n",
    "        left = [[0] * cols for _ in range(cols)]\n",
    "        up = [[0] * cols for _ in range(cols)]\n",
    "\n",
    "        r = c = 0\n",
    "        size = 0 \n",
    "        for i in range(1, cols):\n",
    "            for j in range(1, cols):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1 \n",
    "                    board = min(left[i][j], up[i][j])\n",
    "                    \n",
    "                    while up[i][j-board+1] < board or left[i-board+1][j] < board:\n",
    "                        board -= 1 \n",
    "                    \n",
    "                    if size < board:\n",
    "                        r = i-board\n",
    "                        c = j-board \n",
    "                        size = board\n",
    "        \n",
    "        return [r, c, size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix) + 1\n",
    "        up = [[0] * n for _ in range(n)]\n",
    "        left = [[0] * n for _ in range(n)]\n",
    "        r = c = 0\n",
    "        max_len = 0 \n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n): \n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    up[i][j] = up[i-1][j] + 1 \n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "\n",
    "                    board = min(left[i][j], up[i][j])\n",
    "                    while left[i-board+1][j] < board or up[i][j-board+1] < board:\n",
    "                        board -= 1 \n",
    "                    if max_len < board:\n",
    "                        max_len = board \n",
    "                        r = i-board\n",
    "                        c = j-board\n",
    "                    \n",
    "        return [r,c,max_len] if max_len>0 else []\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if matrix[i - 1][j - 1] == 0:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    if border > size:\n",
    "                        r = i - border\n",
    "                        c = j - border\n",
    "                        size = border\n",
    "        return [r, c, size] if size > 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        # 维护坐标[i,j]位置往上有多少个连续的0,以及往左有多少个连续的0即可\n",
    "        n = len(matrix)\n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        r,c,size = 0,0,0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    left[i][j] = 1\n",
    "                    if j>0:\n",
    "                        left[i][j] += left[i][j-1]\n",
    "                    up[i][j] = 1\n",
    "                    if i>0:\n",
    "                        up[i][j] += up[i-1][j]\n",
    "\n",
    "                    max_len = min(i+1, j+1)\n",
    "                    for k in range(max_len, 0, -1):\n",
    "                        if left[i][j]>=k and left[i-k+1][j]>=k and \\\n",
    "                            up[i][j]>=k and up[i][j-k+1]>=k:\n",
    "                            dp[i][j] = k\n",
    "                            break\n",
    "                    if dp[i][j]>size:\n",
    "                        size = dp[i][j]\n",
    "                        r,c = i-k+1, j-k+1\n",
    "            pass\n",
    "        \n",
    "        return [r,c,size] if size>0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        r,c,size = 0,0,0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    left[i][j] = 1\n",
    "                    if j>0:\n",
    "                        left[i][j] += left[i][j-1]\n",
    "                    up[i][j] = 1\n",
    "                    if i>0:\n",
    "                        up[i][j] += up[i-1][j]\n",
    "                pass\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    max_len = min(i+1, j+1)\n",
    "                    for k in range(max_len, 0, -1):\n",
    "                        if left[i][j]>=k and left[i-k+1][j]>=k and \\\n",
    "                            up[i][j]>=k and up[i][j-k+1]>=k:\n",
    "                            dp[i][j] = k\n",
    "                            break\n",
    "                    if dp[i][j]>size:\n",
    "                        size = dp[i][j]\n",
    "                        r,c = i-k+1, j-k+1\n",
    "                    pass\n",
    "        \n",
    "        return [r,c,size] if size>0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        r,c,size = 0,0,0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    left[i][j] = 1\n",
    "                    if j>0:\n",
    "                        left[i][j] += left[i][j-1]\n",
    "                    up[i][j] = 1\n",
    "                    if i>0:\n",
    "                        up[i][j] += up[i-1][j]\n",
    "\n",
    "                    max_len = min(i+1, j+1)\n",
    "                    for k in range(max_len, 0, -1):\n",
    "                        if left[i][j]>=k and left[i-k+1][j]>=k and \\\n",
    "                            up[i][j]>=k and up[i][j-k+1]>=k:\n",
    "                            dp[i][j] = k\n",
    "                            break\n",
    "                    if dp[i][j]>size:\n",
    "                        size = dp[i][j]\n",
    "                        r,c = i-k+1, j-k+1\n",
    "                    pass\n",
    "                pass\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if matrix[i][j] == 0:\n",
    "        #             max_len = min(i+1, j+1)\n",
    "        #             for k in range(max_len, 0, -1):\n",
    "        #                 if left[i][j]>=k and left[i-k+1][j]>=k and \\\n",
    "        #                     up[i][j]>=k and up[i][j-k+1]>=k:\n",
    "        #                     dp[i][j] = k\n",
    "        #                     break\n",
    "        #             if dp[i][j]>size:\n",
    "        #                 size = dp[i][j]\n",
    "        #                 r,c = i-k+1, j-k+1\n",
    "        #             pass\n",
    "        \n",
    "        return [r,c,size] if size>0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        r, c, size = 0, 0, 0\n",
    "        up = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        left = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    for l in range(min(up[i][j], left[i][j]), 0, -1):\n",
    "                        if up[i][j-l+1] >= l and left[i-l+1][j] >= l:\n",
    "                            cur_size = l\n",
    "                            if cur_size > size:\n",
    "                                r, c, size = i-l, j-l, cur_size\n",
    "        return [r, c, size] if size > 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        pre_matrix = [m.copy() for m in matrix]\n",
    "        n = len(pre_matrix)\n",
    "        m = len(pre_matrix[0])\n",
    "        for i in range(n):\n",
    "            for j in range(1, m):\n",
    "                pre_matrix[i][j] += pre_matrix[i][j - 1]\n",
    "\n",
    "        for j in range(m):\n",
    "            for i in range(1, n):\n",
    "                pre_matrix[i][j] += pre_matrix[i - 1][j]\n",
    "        print(pre_matrix)\n",
    "        res = [-1, -1, -1]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    for k in range(min(n - i, m - j)-1, -1, -1):\n",
    "                        if k < res[2]:\n",
    "                            break\n",
    "                        zero_diff = self.getZeroCount(i, j, k, pre_matrix)\n",
    "                        if k > 2:\n",
    "                            zero_diff -= self.getZeroCount(i + 1, j + 1, k - 2, pre_matrix)\n",
    "                        elif k == 2:\n",
    "                            zero_diff -= matrix[i + 1][j + 1]\n",
    "                        if zero_diff != 0:\n",
    "                            continue\n",
    "                        if k >= res[2]:\n",
    "                            res = [i, j, k + 1]\n",
    "        return res if res[2] != -1 else []\n",
    "\n",
    "    def getZeroCount(self, i, j, k, mat):\n",
    "        zero_diff = mat[i + k][j + k]\n",
    "        if i > 0 and j > 0:\n",
    "            zero_diff = zero_diff - mat[i - 1][j + k] - mat[i + k][j - 1] + \\\n",
    "                        mat[i - 1][j - 1]\n",
    "        elif i > 0:\n",
    "            zero_diff -= mat[i - 1][j + k]\n",
    "        elif j > 0:\n",
    "            zero_diff -= mat[i + k][j - 1]\n",
    "        return zero_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        length = len(matrix)\n",
    "        if length == 0:\n",
    "            return []\n",
    "        prefix = [[0] * (length + 1) for _ in range(length + 1)]\n",
    "        for i in range(0, length):\n",
    "            for j in range(0, length):\n",
    "                prefix[i + 1][j + 1] = matrix[i][j] + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j]\n",
    "        if prefix[-1][-1] == length * length:\n",
    "            return []\n",
    "        rst = []\n",
    "        jishu = list(range(1, length + 1, 2))\n",
    "        left_idx = 0\n",
    "        right_idx = len(jishu) - 1\n",
    "        for mid in range(length, 0, -1):\n",
    "            for i in range(mid, length + 1):\n",
    "                for j in range(mid, length + 1):\n",
    "                    if self.is_square(prefix, i, j, mid):\n",
    "                        return [i - mid, j - mid, mid]\n",
    "        return rst\n",
    "    \n",
    "    def is_square(self, prefix, i, j, length):\n",
    "        if length > 2:\n",
    "            return prefix[i][j] - prefix[i][j - length] - prefix[i - length][j] + prefix[i - length][j - length] == prefix[i - 1][j - 1] - prefix[i - 1][j - length + 1] - prefix[i - length + 1][j - 1] + prefix[i - length + 1][j - length + 1]\n",
    "        else:\n",
    "            return prefix[i][j] - prefix[i][j - length] - prefix[i - length][j] + prefix[i - length][j - length] == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        pre_matrix = [m.copy() for m in matrix]\n",
    "        n = len(pre_matrix)\n",
    "        m = len(pre_matrix[0])\n",
    "        for i in range(n):\n",
    "            for j in range(1, m):\n",
    "                pre_matrix[i][j] += pre_matrix[i][j - 1]\n",
    "\n",
    "        for j in range(m):\n",
    "            for i in range(1, n):\n",
    "                pre_matrix[i][j] += pre_matrix[i - 1][j]\n",
    "        print(pre_matrix)\n",
    "        res = [-1, -1, -1]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    for k in range(min(n - i, m - j)):\n",
    "                        zero_diff = self.getZeroCount(i, j, k, pre_matrix)\n",
    "                        if k > 2:\n",
    "                            zero_diff -= self.getZeroCount(i + 1, j + 1, k - 2, pre_matrix)\n",
    "                        elif k == 2:\n",
    "                            zero_diff -= matrix[i + 1][j + 1]\n",
    "                        if zero_diff != 0:\n",
    "                            continue\n",
    "                        if k >= res[2]:\n",
    "                            res = [i, j, k + 1]\n",
    "        return res if res[2] != -1 else []\n",
    "\n",
    "    def getZeroCount(self, i, j, k, mat):\n",
    "        zero_diff = mat[i + k][j + k]\n",
    "        if i > 0 and j > 0:\n",
    "            zero_diff = zero_diff - mat[i - 1][j + k] - mat[i + k][j - 1] + \\\n",
    "                        mat[i - 1][j - 1]\n",
    "        elif i > 0:\n",
    "            zero_diff -= mat[i - 1][j + k]\n",
    "        elif j > 0:\n",
    "            zero_diff -= mat[i + k][j - 1]\n",
    "        return zero_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        dp = [[[0, 0] for _ in range(n+1)] for _ in range(n+1)]\n",
    "        ans = []\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    dp[i][j][0] = dp[i-1][j][0] + 1\n",
    "                    dp[i][j][1] = dp[i][j-1][1] + 1\n",
    "                    upper = min(dp[i][j])\n",
    "                    for k in range(upper):\n",
    "                        if min(dp[i-k][j][1], dp[i][j-k][0]) >= k+1:\n",
    "                            if not ans or k+1 > ans[2]:\n",
    "                                ans = [i-k-1, j-k-1, k+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n,ans=len(matrix),[]\n",
    "\n",
    "        dp=[[[0,0] for _ in range(n+1)] for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if matrix[i-1][j-1]==0:\n",
    "                    dp[i][j][0]=dp[i][j-1][0]+1\n",
    "                    dp[i][j][1]=dp[i-1][j][1]+1\n",
    "                    border=min(dp[i][j])\n",
    "                    while dp[i-border+1][j][0]<border or dp[i][j-border+1][1]<border:\n",
    "                        border-=1\n",
    "                    # ans=max(ans,dp[i][j])\n",
    "                    if ans:\n",
    "                        if border>ans[-1]:\n",
    "                            ans=[i-border,j-border,border]\n",
    "                    else:\n",
    "                        ans=[i-border,j-border,border]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        rows,cols=len(matrix),len(matrix[0])\n",
    "        # dp[i][j]=[a,b] a is the right line, b is the bottom line\n",
    "        # dp[i][j]表示以i,j为右下角的方阵，上右方a和左下方b的连续0长度\n",
    "        dp=[[[0,0] for _ in range(cols+1)] for _ in range(rows+1)] #边界处理\n",
    "        # dp数组初始化\n",
    "        for i in range(1,rows+1):\n",
    "            for j in range(1,cols+1):\n",
    "                if matrix[i-1][j-1]==0:\n",
    "                    dp[i][j][0]=dp[i-1][j][0]+1\n",
    "                    dp[i][j][1]=dp[i][j-1][1]+1\n",
    "        r,c,size=-1,-1,0\n",
    "        for i in range(1,rows+1):\n",
    "            for j in range(1,cols+1):\n",
    "                if matrix[i-1][j-1]==0: # 其实个人认为这行无所谓要不要，看别的题解都有这个判断，无非就是优化了一点时间\n",
    "                    t_size=min(dp[i][j]) # 因为是方阵 所以取最短边\n",
    "                    while t_size>size:\n",
    "                        #判断两边长度能否满足这个最短边的长度\n",
    "                        if dp[i-t_size+1][j][1]>=t_size and dp[i][j-t_size+1][0]>=t_size:\n",
    "                            r,c=i-t_size,j-t_size\n",
    "                            size=t_size\n",
    "                            break\n",
    "                        t_size-=1\n",
    "        if size==0:\n",
    "            return []\n",
    "        return [r,c,size]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        rows,cols=len(matrix),len(matrix[0])\n",
    "        # dp[i][j]=[a,b] a is the right line, b is the bottom line\n",
    "        # dp[i][j]表示以i,j为右下角的方阵，上右方a和左下方b的连续0长度\n",
    "        dp=[[[0,0] for _ in range(cols+1)] for _ in range(rows+1)] #边界处理\n",
    "        # dp数组初始化\n",
    "        for i in range(1,rows+1):\n",
    "            for j in range(1,cols+1):\n",
    "                if matrix[i-1][j-1]==0:\n",
    "                    dp[i][j][0]=dp[i-1][j][0]+1\n",
    "                    dp[i][j][1]=dp[i][j-1][1]+1\n",
    "        r,c,size=-1,-1,0\n",
    "        for i in range(1,rows+1):\n",
    "            for j in range(1,cols+1):\n",
    "                if matrix[i-1][j-1]==0: # 其实个人认为这行无所谓要不要，看别的题解都有这个判断，无非就是优化了一点时间\n",
    "                    t_size=min(dp[i][j]) # 因为是方阵 所以取最短边\n",
    "                    while t_size>size:\n",
    "                        #判断两边长度能否满足这个最短边的长度\n",
    "                        if dp[i-t_size+1][j][1]>=t_size and dp[i][j-t_size+1][0]>=t_size:\n",
    "                            r,c=i-t_size,j-t_size\n",
    "                            size=t_size\n",
    "                            break\n",
    "                        t_size-=1\n",
    "        if size==0:\n",
    "            return []\n",
    "        return [r,c,size]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n, ret, curMax= len(matrix), [], 0\n",
    "        dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]\n",
    "        # dp[i][j][row, col]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    dp[i][j] = [0, 0]\n",
    "                else:\n",
    "                    dp[i][j][1] = 1 if i == 0 else (dp[i - 1][j][1] + 1)\n",
    "                    dp[i][j][0] = 1 if j == 0 else (dp[i][j - 1][0] + 1)\n",
    "\n",
    "        # print (dp)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                size = min(dp[i][j][0], dp[i][j][1])\n",
    "                if size <= curMax:\n",
    "                    continue\n",
    "                for k in range(size - 1, curMax - 1, -1):\n",
    "                    if dp[i - k][j][0] > k and dp[i][j - k][1] > k:\n",
    "                        if k >= curMax:\n",
    "                            curMax = k + 1\n",
    "                            ret = [i - k, j - k, k + 1]\n",
    "                        break    \n",
    "                    \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        A = [[[0, 0] for _ in range(m)] for _ in range(n)]\n",
    "        B = [[[0, 0] for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 1: continue\n",
    "                A[i][j][0], A[i][j][1] = 1, 1\n",
    "                if i == 0 and j == 0: continue\n",
    "                if i == 0: A[i][j][0] += A[i][j - 1][0]\n",
    "                elif j == 0: A[i][j][1] += A[i - 1][j][1]\n",
    "                else:\n",
    "                    A[i][j][0] += A[i][j - 1][0]\n",
    "                    A[i][j][1] += A[i - 1][j][1]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                if matrix[i][j] == 1: continue\n",
    "                B[i][j][0], B[i][j][1] = 1, 1\n",
    "                if i == n - 1 and j == m - 1: continue\n",
    "                if i == n - 1: B[i][j][0] += B[i][j + 1][0]\n",
    "                elif j == m - 1: B[i][j][1] += B[i + 1][j][1]\n",
    "                else:\n",
    "                    B[i][j][0] += B[i][j + 1][0]\n",
    "                    B[i][j][1] += B[i + 1][j][1]\n",
    "        def calc(i, j):\n",
    "            x, y = i, j\n",
    "            res = -1\n",
    "            b = min(B[i][j])\n",
    "            a = min(A[i + b - 1][j + b - 1])\n",
    "            if a >= b: \n",
    "                res = max(b, res)\n",
    "\n",
    "            a = min(A[i][j])\n",
    "            b = min(B[i - a + 1][j - a + 1])\n",
    "            if b >= a and a >= res:\n",
    "                res = a\n",
    "                x, y = i - a + 1, j - a + 1\n",
    "            return (res, x, y)\n",
    "        r, c, size = 0, 0, 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 1: continue\n",
    "                s, a, b = calc(i, j)\n",
    "                if s > size: r, c, size = a, b, s\n",
    "                elif s == size:\n",
    "                    if r > a: r, c = a, b\n",
    "                    elif r == a and c > b: r, c = a, b\n",
    "        if size == 0: return []\n",
    "        return [r, c, size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:return []\n",
    "        mxrow=defaultdict(int)\n",
    "        mxcol=defaultdict(int)\n",
    "        rows,cols=len(matrix),len(matrix[0])\n",
    "        res=[]\n",
    "        for r in range(rows)[::-1]:\n",
    "            for c in range(cols)[::-1]:\n",
    "                if matrix[r][c]==0:\n",
    "                    mxrow[r,c]=1+mxrow[r,c+1]\n",
    "                    mxcol[r,c]=1+mxcol[r+1,c]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if matrix[r][c]==0:\n",
    "                    mxsize=min(mxrow[r,c],mxcol[r,c])\n",
    "                    cursize=0 if not res else res[2]\n",
    "                    for size in range(mxsize,cursize,-1):\n",
    "                        if mxcol[r,c+size-1]>=size and mxrow[r+size-1,c]>=size:\n",
    "                            res=[r,c,size]\n",
    "                            break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        mxrow = defaultdict(int)\n",
    "        mxcol = defaultdict(int)\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        res = []\n",
    "        for r in range(rows)[::-1]:\n",
    "            for c in range(cols)[::-1]:\n",
    "                if matrix[r][c] == 0:\n",
    "                    mxrow[r, c] = 1 + mxrow[r, c + 1]\n",
    "                    mxcol[r, c] = 1 + mxcol[r + 1, c]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if matrix[r][c] == 0:\n",
    "                    mxsize = min(mxrow[r, c], mxcol[r, c])\n",
    "                    cursize = 0 if not res else res[2]\n",
    "                    for size in range(mxsize, cursize, -1):\n",
    "                        if mxcol[r, c + size - 1] >= size and mxrow[r + size - 1, c] >= size:\n",
    "                            res = [r, c, size]\n",
    "                            break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        mxrow = defaultdict(int)\n",
    "        mxcol = defaultdict(int)\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        res = []\n",
    "        for r in range(rows)[::-1]:\n",
    "            for c in range(cols)[::-1]:\n",
    "                if matrix[r][c] == 0:\n",
    "                    mxrow[r, c] = 1 + mxrow[r, c + 1]\n",
    "                    mxcol[r, c] = 1 + mxcol[r + 1, c]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if matrix[r][c] == 0:\n",
    "                    mxsize = min(mxrow[r, c], mxcol[r, c])\n",
    "                    cursize = 0 if not res else res[2]\n",
    "                    for size in range(mxsize, cursize, -1):\n",
    "                        if mxcol[r, c + size - 1] >= size and mxrow[r + size - 1, c] >= size:\n",
    "                            res = [r, c, size]\n",
    "                            break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findSquare(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        mxrow = defaultdict(int)\n",
    "        mxcol = defaultdict(int)\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        res = []\n",
    "        for r in range(rows)[::-1]:\n",
    "            for c in range(cols)[::-1]:\n",
    "                if matrix[r][c] == 0:\n",
    "                    mxrow[r, c] = 1 + mxrow[r, c + 1]\n",
    "                    mxcol[r, c] = 1 + mxcol[r + 1, c]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if matrix[r][c] == 0:\n",
    "                    mxsize = min(mxrow[r, c], mxcol[r, c])\n",
    "                    cursize = 0 if not res else res[2]\n",
    "                    for size in range(mxsize, cursize, -1):\n",
    "                        if mxcol[r, c + size - 1] >= size and mxrow[r + size - 1, c] >= size:\n",
    "                            res = [r, c, size]\n",
    "                            break\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
